package com.github.yangyishe.p300;

/**
 * 240. 搜索二维矩阵 II
 * https://leetcode.cn/problems/search-a-2d-matrix-ii/description/?envType=study-plan-v2&envId=top-100-liked
 *
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 *
 * 每行的元素从左到右升序排列。
 * 每列的元素从上到下升序排列。
 *
 *
 * 示例 1：
 *
 *
 * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
 * 输出：true
 * 示例 2：
 *
 *
 * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
 * 输出：false
 *
 *
 * 提示：
 *
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= n, m <= 300
 * -109 <= matrix[i][j] <= 109
 * 每行的所有元素从左到右升序排列
 * 每列的所有元素从上到下升序排列
 * -109 <= target <= 109
 */
public class Problem240 {
    public static void main(String[] args) {
        int[][] matrix=new int[][]{
                {1,4,7,11,15},
                {2,5,8,12,19},
                {3,6,9,16,22},
                {10,13,14,17,24},
                {18,21,23,26,30}
        };
        int target=11;

        Problem240 problem240 = new Problem240();
        boolean searchMatrix = problem240.searchMatrix(matrix, target);
        System.out.println("searchMatrix = " + searchMatrix);
    }

    /**
     * 思路：
     * 仿效二分查找法的思路
     * 参数二维矩阵有一个特点，任取一个坐标x,y
     * 1. 对于所有的m<=x,n<=y,都有matrix[m][n]<=matrix[x][y]
     * 2. 对于所有的m>=x,n>=y,都有matrix[m][n]>=matrix[x][y]
     * 通过此特性，可将搜索区域拆分成4块：左上，右上，左下，右下
     *
     * 如果走到最后，则排除左上和右上的所有数据，再对左下和右上两块儿数据，分别进行搜索。
     * 如果左上和右下没有任何数据，则直接返回false
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        //1. 确定两个大小点，保证大小点之间的横纵坐标最多差1
        int height=matrix.length;
        int width=matrix[0].length;

        return searchZone(matrix,0,0,height-1,width-1,target);
    }

    public boolean searchZone(int[][] matrix,int minRow,int minCol,int maxRow,int maxCol,int target){
        if(minRow>maxRow||minCol>maxCol){
            return false;
        }
        int leftRow=minRow,leftCol=minCol,rightRow=maxRow,rightCol=maxCol;
        if(matrix[leftRow][leftCol]>target){
            return false;
        }else if(matrix[leftRow][leftCol]==target){
            return true;
        }
        if(matrix[rightRow][rightCol]<target){
            return false;
        }else if(matrix[rightRow][rightCol]==target){
            return true;
        }

        int midRow,midCol;
        while(leftRow+1<rightRow||leftCol+1<rightCol){
            midRow=(leftRow+rightRow)/2;
            midCol=(leftCol+rightCol)/2;
            if(matrix[midRow][midCol]==target){
                return true;
            }else if(matrix[midRow][midCol]>target){
                rightRow=midRow;
                rightCol=midCol;
            }else{
                leftRow=midRow;
                leftCol=midCol;
            }

        }

        return searchZone(matrix, leftRow+1, minCol, maxRow, rightCol-1, target)||searchZone(matrix,minRow,leftCol+1,rightRow-1,maxCol,target);
    }
}
